package com.sfx.算法专题.滑动窗口.变化窗口;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-08-03
 * Time: 23:06
 */
public class Code_1_minSubArrayLen {

    /**
     * 题眼:
     *      1.全部为正整数
     * 方法一:
     *      1): 暴力枚举策略O(N^2)
     *  枚举所有子数组 固定一个left,使用right往后遍历,寻找符合条件的sum,继续移动left,
     *  right从left+1继续 , 直到所有的子数组全部遍历完成,left到达结尾
     *  根据暴力枚举寻找优化策略
     *  (1) : 使用sum累加
     *  (2) : 如果sum累加结果已经>=target,right就不用在往后移动了,因为长度越来越长了
     *  (3) : 当到下一个子数组的时候,right不用移动到left的下一个,不需要移动,只需要在移动
     *       left的时候,将sum-=arr[left]即可  --->即使用单调性,right不回退,同向双指针
     *       同向双指针也叫作 "滑动窗口"
     *       使用同向双指针 绝大部分都是 维护一段区间,两个指针移动的时候,就形象于 "窗口"
     *   滑动窗口特点(什么时候使用滑动窗口) :
     *   1.滑动窗口 本质上就是 "同向双指针"
     *   2.当暴力方法的时候 "两个指针" 都不回退---> 具有单调性
     *   如何使用滑动窗口 ?
     *      初始化两个指针=0 left为左端点,right为右端点
     *      while(边界条件) {
     *          2. 进窗口->right先移动,移动到最佳位置,在移动left
     *          3. 判断是否符合条件,是否要出窗口
     *      }
     *   总结: 利用 "单调性" -> 先让right指针移动,移动到最佳位置,在移动left

     *    滑动窗口的正确性 :
     *      利用了单调性,规避了许多没有必要的枚举行为
     *    时间复杂度 : O(2*N) --> O(N) 最差情况下:right移动到结尾,left在移动到结尾
     */

    static class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            //1.定义两个指针
            int left = 0;
            int right = 0;
            int sum = 0;
            int res = Integer.MAX_VALUE;
            //2.两指针同向移动
            while(right < nums.length) {
                sum += nums[right];
                right ++;
                while(sum >= target) {
                    res = Math.min(res,right - left);
                    sum -= nums[left];
                    left++;
                }
            }
            return res == Integer.MAX_VALUE ? 0 : res;
        }
    }
}